1. Field of the Invention
The present invention relates to transport of router advertisement messages specifying routing information between Internet Protocol (IP) routers according to a prescribed distance vector routing protocol.
2. Description of the Related Art
Wide area packet switched networks such as the Internet have become an integral part of worldwide commerce in part due to the ability of different networks to interoperate without central control. In particular, the decentralization of control is possible due to routing protocols which enable routers to communicate amongst each other and share routing information: routing protocols include operations such as router advertisement, router discovery, link state advertisement, and the sharing of all or at least a portion of respective routing tables.
Numerous routing protocols have been developed to satisfy various design requirements, including optimality (selecting the optimal route), simplicity and low overhead to minimize burden on system resources, robustness and stability (i.e., maintaining operability despite failures within the network), rapid convergence, and flexibility in adapting to network changes.
Convergence is the process of agreement, by all routers, on optimal routes. When a network event causes routes to change to either an available or unavailable state, routers will distribute routing update messages, causing recalculation of optimal routes and eventually causing all routers to agree on these routes. Routing protocols that converge slowly can cause routing loops or network outages.
Link-state protocols (also known as shortest path first protocols) flood routing information to all nodes in the network. Each router, however, sends only the portion of the routing table that describes the state of its own links. In link-state protocols, each router builds a model of the entire network topology in its routing tables. An example of a link-state protocol is Open Shortest Path First (OSPF) Protocol, described in the Internet Engineering Task Force (IETF) Request for Comments (RFC) 2328, available at the IETF website address “www.ietf.org/rfc/rfc2328.txt”.
Although link-state protocols enable each router to build a topology table that provides a detailed representation of the entire network topology, link-state protocols require more system resources (e.g., CPU utilization and memory) than distance vector protocols. For example, link-state protocols such as OSPF require synchronization of all topology tables between the respective routers. In addition, OSPF requires a strict topology hierarchy, where nodes grouped into “areas” (e.g., Area 1, Area 2, Area 3, etc.), where each area can communicate only through a backbone area (Area 0), and where each area interfaces with the backbone area via at least one corresponding access border router (ABR).
Hence, the topology constraints of OSPF preclude its deployment in less-structured networks such as ad hoc networks.
Distance vector routing protocols call for each router to send all or a portion of its routing table in a routing update message at regular intervals to each of its neighboring (i.e., next-hop) routers. Hence, each router can build a topology table that provides a detailed representation of the network topology relative to the corresponding router, and a routing table that enables routing of packets according to the network topology. Hence, routers employing distance vector routing protocols send updates only to neighboring routers; consequently, a router having received an update from a neighboring router (according to a distance vector routing protocol) will be unable to determine any attributes of the network beyond the neighboring router. An example of a distance vector routing protocol is the Routing Information Protocol (RIP), described in the Internet Engineering Task Force (IETF) Request for Comments (RFC) 1723, available at the IETF website address “www.ietf.org/rfc/rfc1723.txt”.
Another routing protocol is the flooding distance vector protocol, where routing update messages specifying only reachability information are flooded throughout the network, in the same manner as flooding is performed in the link-state protocols. Note, however, that flooding distance vector routing update messages do not include any topology information, but only reachability information (e.g., a given address is reachable via the router at a specified cost such as distance from the router to the destination). Further, the flooding distance vector protocol does not limit the dissemination of the routing update messages throughout the network; hence, the flooding distance vector routing protocol is susceptible to the formation of loops, where the same destination can be accessed by alternate links.
A particular problem encountered by the distance vector protocol and the flooding distance vector protocol is a “count to infinity” problem, where neighboring nodes will distribute stale information among each other, incrementing the distance to a given destination each time, until the recorded distance exceeds a maximum allowable distance (i.e., “infinity”).
FIG. 1 is a diagram illustrating a network 10 having routers 12 (e.g., 12a, 12b, 12c, 12d, 12e, 12f) configured for sending routing update messages according to a flooding distance vector protocol. Assume for example that each of the routers 12 is configured for sending routing update messages according to RIP. In a standard distance vector protocol, a given router (e.g., 12b) would send a router advertisement message to its neighboring routers (e.g., 12a, 12c) specifying only reachability information, for example that it can reach router 12f at some specified cost (e.g., 1 hop). In response to receiving the router advertisement message, the neighboring routers (e.g., 12a, 12c) would output respective router advertisement messages specifying that the router 12f was reachable at an added cost (e.g., 2 hops). The router advertisement messages are thus propagated throughout the network 10.
If the path 14 from router 12b to 12f fails following distribution of the above-described router advertisement messages, such that the router 12f is not reachable by any mechanism (e.g., the router 12f itself fails), the router 12b will detect that the router 12f is no longer reachable via the default interface providing a cost of 1 hop: in response, the router 12b will install the route advertised by the router 12a as its default route for reaching the router 12f, and output an updated router advertisement message specifying that the router 12f is reachable via the router 12b at a cost of 3 hops, based on the router advertisement message from the router 12a. The remaining routers 12a, 12c, 12d, and 12e update their respective routing tables and output updated router advertisement messages with increasing costs; as each route to the router 12f is determined to be invalid (due to a time out due to inactivity of the path), the routers continually select another route to the router 12f and specifying an increased cost, resulting in an infinite loop that results in the “count to infinity”.
Attempts at solving the problem by defining infinity to be the numerical value of fifteen (“15”) have not been successful, due to the fact that the count to infinity problem still results in an unacceptable delay before network convergence is completed. Another attempt to prevent the count to the infinity problem involves implementing a hold down state for a prescribed interval before accepting alternate paths.
Assume further that the router 12e receives both router advertisement messages from the routers 12a and 12c, and chooses the path to the destination router 12f via the router 12a, as opposed to the path via the router 12d. If the path from router 12b to 12f fails, the router 12e will receive an update from the router 12a specifying that the route is no longer reachable; once the route has been marked as unreachable, the router 12e can place the route in a “hold down” state, where the router 12e will not accept any higher cost paths to the router 12f from any source for at least as long as it would normally take for any false routing information to time out of the system, typically measured in terms of a prescribed number of minutes. Once this hold down state has passed, the router 12e can begin accepting new alternate paths towards the router 12f (in this case the path via the router 12d), and install the alternate path.
In many applications such as mobile ad hoc networking, however, the hold down time is undesirable because it slows down network convergence, causing the router 12e to be unable to reach the router 12f for the entire period of the hold down interval.
The above-described columns are exacerbated in a flooded distance vector protocol, where a router floods the network not only with its own routing update message, but also with any routing update message received by that router from another router.